package com.mamingchao.issue.graph;

import java.util.*;

/**
 * 大前提，无向图
 * 从图生成最小生成树
 *
 *
 * Created by mamingchao on 2024/7/26.
 */
public class MinimumSpanningTree {


    public HashSet<GraphEdge> k(Graph graph){

        HashSet<GraphEdge> result = new HashSet<>();

        // 第一步，将图里面所有的边，都放进堆里；按照边的权重大小排序
        // 每个node，都自己是一个集合
        // 第二步，按照权重从小到大依次取边；from 和 to 的两个node 如果不在同一个集合中，就合并，并保留住这个edge
        // 如果这个边的 from 和to 这两个node 已经在一个集合里了，这个edge 则抛弃


        PriorityQueue<GraphEdge> heap = new PriorityQueue<>(new GraphEdgeComparator());
        for (GraphEdge edge : graph.getGraphEdges()) {
            heap.add(edge);
        }

        // key 为每一个node ， value 为 该node所在的集合
        HashMap<GraphNode, HashSet<GraphNode>> node2NodeSetMap = new HashMap<>();

        for (Map.Entry<Integer, GraphNode> nodeEntry : graph.getGraphNodes().entrySet()) {
            HashSet<GraphNode> sets = new HashSet<>();
            sets.add( nodeEntry.getValue());

            node2NodeSetMap.put(nodeEntry.getValue(), sets);
        }


        while (!heap.isEmpty()) {
            GraphEdge edge = heap.poll();
            GraphNode from = edge.getFrom();
            GraphNode to = edge.getTo();

            HashSet fromSets = node2NodeSetMap.get(from);
            HashSet toSets = node2NodeSetMap.get(to);

            // 如果from node 所在的集合 中有 to node，说明这个节点已经在有边 链接了他们，就不
            if (fromSets.contains(to)) {
                continue;
            } else {
                result.add(edge);
                // 合并 两个集合
            }




        }

        return result;
    }



    private class FakeUnionFindSet{

        public boolean isSameSet(HashSet o1, HashSet o2) {
            return o1 == o2;
        }

        public void uionSet(HashSet o1, HashSet o2){

            if (!o1.isEmpty()){

            }

        }
    }

    // asc 升序排列
    private class  GraphEdgeComparator implements Comparator<GraphEdge> {

        @Override
        public int compare(GraphEdge o1, GraphEdge o2) {
            if (o1.getWeight() > o1.getWeight()) {
                return 1;
            } else if (o1.getWeight() == o1.getWeight()){
                return 0;
            } else {
                return -1;
            }
        }
    }



}
